#include "../include/steiner.h"
#include <stdlib.h>
#include <string.h>
#include <stdio.h>

int isTerm(int * terms, int nterms, int bscado) {
  int i;
  for (i=0;i<nterms;i++) {
    if (bscado == terms[i]) {
      return 1;
    };
  };
  return 0;
};

int buscaLocal(int ** saida, int * entrada, graph * g, int tament, int * tamsaida, int * terms, int nterms) {

  char     boolean;
  int      j,i,k,l;
  int      *dados;
  int      *ant;
  int      tamant;
  int      tamdados;
  graph    *d;
  int      custoDado;
  int      custo;
  int      * resultante;
  int      tamres;

  ant   = (int *) malloc(sizeof(int)*g->TotalNodes);
  dados = (int *) malloc(sizeof(int)*g->TotalNodes);
  resultante = (int *) malloc(sizeof(int)*g->TotalNodes);

  memcpy(ant,entrada,tament*sizeof(int));
  tamant = tament;
  
  d = (graph *) malloc(sizeof(graph));
  initializeGraph(d,tament);

  //  printf("a\n");

  for (j=0;j<tament;j++) {
    for (k=0;k<tament;k++) {
      d->adjacency[j][k] = g->adjacency[entrada[j]][entrada[k]];
      d->adjacency[k][j] = g->adjacency[entrada[k]][entrada[j]];
    };
  };

  //  printf("b\n");
  
  custoDado = MinPrimGraph(d);

  //  printf("b\n");

  freeGraph(d);

  do {
    boolean = 0;
    j = 0;
    memcpy(resultante,ant,tamant*sizeof(int));
    tamres = tamant;
    for (i=0;i<(g->TotalNodes);i++) {
      if (isTerm(terms,nterms,i)) {
	j++;
      } else {
	if (j >= tamant) {
	  memcpy(dados,ant,tamant*sizeof(int));
	  dados[j] = i;
	  tamdados = tamant + 1;
	} else if (i < ant[j]) {
	  if (j > 0) {
	    memcpy(dados,ant,j*sizeof(int));
	  };
	  dados[j] = i;
	  memcpy(&(dados[j+1]),&(ant[j]),(tamant-j+1)*sizeof(int));
	  tamdados = tamant + 1;
	} else if (i == ant[j]) {
	  memcpy(dados,ant,j*sizeof(int));
	  memcpy(&(dados[j]),&(ant[j+1]),(tamant-j)*sizeof(int));
	  tamdados = tamant - 1;
	  j++;
	};
	d = (graph *) malloc(sizeof(graph));	
	initializeGraph(d,tamdados);
	
	for (l=0;l<tamdados;l++) {
	  for (k=0;k<tamdados;k++) {
	    d->adjacency[l][k] = g->adjacency[dados[l]][dados[k]];
	    d->adjacency[k][l] = g->adjacency[dados[k]][dados[l]];
	  };
	};

	//	printf("%d,%d\n",i,j);

	custo = MinPrimGraph(d);

	if (custo >= 0) {
	  if (custo < custoDado) {
	    custoDado = custo;
	    memcpy(resultante,dados,sizeof(int)*tamdados);
	    tamres = tamdados;
	    boolean = 1;
	    /* freeGraph(d);
	       break;*/
	  };
	};
	
	freeGraph(d);
	
      };
    };
    tamant = tamres;
    memcpy(ant,resultante,sizeof(int)*tamres);
  } while (boolean);

  *saida = ant;
  (*tamsaida) = tamant;
  free(dados);
  free(resultante);
  
  return custoDado;
};
